package 双指针技巧与相关题目;

// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
// 返回容器可以储存的最大水量
// 说明：你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/

public class Code05_ContainerWithMostWater {

    /**
     *       l1       r1
     * 0  1  2  3  4  5  6  7  8  9 ...
     *       l                    r
     * 假如 l1, r1 位置是最优解，在滑动的过程中，要么 l先来到 l1位置，要么 r先来到 r1位置
     * 假如 l 来到 l1位置，但是 r还没来到 r1位置，而是处于右侧的某一个位置
     * 那么会不会错过这个答案呢，不会！
     * 因为如果是错过这个答案的情况就是在 r 没有来到 r1位置之前，l位置动了，即 l来到 l1位置的右侧
     * 那么只能说明找到了最大的水量 , 因为只有小的位置会动，所以说明 l1 位置的数 比当前 r位置的数小
     */

    // 时间复杂度O(n)，额外空间复杂度O(1)
    public static int maxArea(int[] height) {
        int ans = 0;
        for(int l = 0, r = height.length - 1; l < r; ){
            // l,r 两边位置谁小就先结算谁，以小的那一边作为高度
            ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
            if(height[l] <= height[r]){
                l++;
            }else {
                r--;
            }
        }
        return ans;
    }
}
